package _02_并查集;
/*
    并查集的公共父类
 */
public abstract class UnionFind {
    protected int[] parents; //每个索引存放根节点的数组
    public UnionFind(int capacity){
        if(capacity<0){
            throw new IllegalArgumentException("capacity must be >= 1");
        }
        parents = new int[capacity];
        //初始化每个集合，每一个元素都属于一个集合
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
    }

    /**
     * 查找v所属的集合(根节点)
     * O(1)
     * @param v
     * @return 返回它所存储的元素即可，也就是根节点
     */
    public abstract int find(int v);

    /**
     * 合并v1,v2所属的集合,将v1合并到v2
     * 如果v1之前属于了一个集合，那么将整个数组都和v1属于同一个集合的元素都合并到v2
     * @param v1
     * @param v2
     */
    public abstract void union(int v1,int v2);

    /**
     * 检查v1和v2是否属于同一个集合
     * @param v1
     * @param v2
     * @return
     */
    public boolean isSame(int v1,int v2){
        return find(v1) == find(v2);
    }

    //检查元素是否超过数组索引
    protected void rangeCheck(int v){
        if(v<0 || v>=parents.length){
            throw new IllegalArgumentException("v is out ou bounds");
        }
    }
}
